To aid the understanding of the following description, some terms to be used later in the text will be defined below. As far as possible, the description of the invention is written using concurrent terminology of the English-language literature of the art.
A switch matrix is comprised of a plurality of switch elements which may be Identical or different from each other and which elements are interconnected according to a given topology. In the literature of the art, such a switch matrix may also be called a "switching network", since the switch elements form a network having the given topology. Hence, a switch matrix is considered to have a defined form when its switch elements and their interconnections are known.
Switch elements may be treated as the elementary "building blocks" from which the switch matrix is constructed by connecting a plurality of switch elements into a switching network comprising said plurality of switch elements connected in parallel and in series. A set of mutually parallel switch elements forms a switch stage. Switch elements of consecutive switch stages are connected to each other by internal connections (links) of the switch matrix in accordance with the above-mentioned topology.
In its comprehensive meaning, the term switch Is used to denote the entity configured about a switching matrix. Hence, a switch can denote any means employed for signal switching in a communications network. With regard to the context of the present invention, the switch concerned herein is a packet switch inasmuch the invention is related to switching in a packet-switched communications network, particularly an ATM network. Depending on the case, a switch may also be called a switching system.
ATM (Asynchronous Transfer Mode) is a connection-oriented packet-switching technique, which is selected by the international organization of telecommunications standardization ITU-T as the target transfer mode solution for implementing a broadband multimedia network (B-ISDN). In an ATM network, the problems of conventional packet-switched networks (such as X.25 networks) are overcome by transmitting short packets of a constant length (53 bytes) called cells Each cell comprises a 48 byte payload portion and a 5 byte header. Further discussion of an ATM network herein will be omitted as a nonessential subject to the understanding of the invention. When required, a closer description of this topic can be found in international standards and textbooks of the art.
Switches developed for the needs of a conventional TDM (Time Division Multiplex) network, a kind of an STM (Synchronous Transfer Mode) network, cannot be directly utilized for switching tasks in an ATM network. Neither are switch designs developed for conventional packet-switched networks suitable for switching purposes in an ATM network. Besides the fixed cell length and the limited functionality of the cell header field, the choice of an optimal switching architecture for an ATM network is also affected by the statistical behaviour of the cell stream and the high speed (typically in the order of 150-600 Mbit/s) required from an ATM switch.
FIG. 1 shows an ATM switch, seen, from the outside. The switch has n input ports I.sub.1 -I.sub.n and m output ports O.sub.1 -O.sub.m. A cell stream CS is present at each port of the ATM switch 11. The header of an individual cell in the data stream is denoted by symbol HD. In the ATM switch, the cells are switched from the input port I.sub.i to the output port I.sub.j and simultaneously the value of the cell header is translated from an incoming value to an outgoing cell. For this purpose, the switch includes a translation table 12 by means of which said header translation is made. From the table can be seen that, e.g., all the cells received at input port I.sub.1 and having a header with a value X are switched onto output port O.sub.1, whereby the header of the outgoing cells is simultaneously given value K. Cells present on different input ports may have headers of equal value; e.g. cells received at input port I.sub.n with the same header value X are also switched onto output port O.sub.1, but their header is given value J on the output port.
Hence, the, main tasks of a switch are: switching of cells (packets) from the input port onto a desired output port and the required "header switching", that is, header translation. Occasionally, as is also evident from the figure, two cells may be simultaneously contending for access onto the same outgoing port. For this purpose, the switch must have buffer capacity so that there is no need for discarding cells under this kind of a condition. Accordingly, the third main task of the switch is to provide the required buffer capacity. In fact, different switch designs can be categorized by the implementation method of these three main tasks and the stage of the switch containing said implementation.
While ATM switch architectures can be categorized by a great number of different criteria, only those related more closely to the switch configuration according to the present invention will be described in this context, thus helping the reader to understand the description given below.
One of the main decisions required in the design of a switch architecture is the type of switching fabric to be employed. The different alternatives can be categorized in two major classes: single-stage and multistage switching fabrics. In single-stage switches, the input and output ports are connected to each other via a single stage only. Then, also packet switching takes place in a single stage only. As switch designs may in reality have hundreds or even thousands of input and output ports, their practical implementations are typically of the multistage type. In a multistage switch, switching is carried out by switch elements arranged in multiple stages.
Multistage switches may be further subdivided into single-path and multiple-path types depending on whether a single path or multiple paths is/are provided between a given input port and a given destination port. Multistage switching fabrics are also frequently denoted by abbreviation MIN (Multistage Interconnection Network). As the switching fabric according to the invention is of the multistage type, the description below relates only to multistage switching fabrics (MINs).
Another design choice to be made concerns the internal structure of the MIN which may internally connection-oriented or connectionless. It must be noted herein that, while the ATM network in itself is implemented using a connection-oriented packet-switching technique, the switch used therein can anyhow be internally connectionless.
A still another characterizing property of a switch is the location of routing information. One possibility is to store the routing information locally in the switch element memory in the form of routing tables, whereby each switch element can, based thereon, individually perform the translation of the virtual channel identifier (VCI). According to another approach, the routing information is contained in a self-routing tag, which is added to the cell at the input edge of the switch.
In a connection-oriented switch, path routing takes place in a preset manner already in the establishment phase of the connection (hence known as preset path routing), whereby all cells belonging to the same virtual connection will pass via the preset path. If the routing scheme keeps the routing information in routing tables of the switch elements, the tables are updated during the establishment of the connection. Respectively, if the routing information is included in the self-routing tag of the cell, this identifier which serves to determine cell routing in a unique manner is attached to the cell at the input edge of the switch.
In a connectionless switch, the routing decision is made separately per each cell. This means that cells belonging to the same virtual connection can pass through the switch via different routes. Also herein, the routing information can be placed in the routing tables of the individual switch elements, or alternatively, the cell can be tagged with the routing information by attaching the above-mentioned identifier tag to the cell. Then, the significant bits of the tag have no fixed role in the routing operation, but instead, a switch element recognizing those bits can route the cell either in a randomized manner or according to a given algorithm. If the switch can offer several connection paths, the cell stream may be shared statistically evenly over all available paths, thus reducing the probability of internal blocking.
Today, two different approaches are utilized in the design of ATM switches in order to avoid congestion due to internal blocking.
According to the first approach, the switch uses a great number of internal links or switch elements in its internal stages. However, with the increasing number of internal links or switch elements, the switch structure becomes complicated making the implementation of large switches very clumsy. An example of this principle is presented by the switch disclosed in U.S. Pat. No. 4,955,016 known as a growable Knockout switch.
According to the second approach, the switching matrix is formed by switch elements complemented with individual output buffers or shared buffers. This principle requires a complicated arrangement of buffer control. Moreover, large-capacity buffers are needed to assure a sufficient service quality, whereby the cell propagation delay increases and the switch element becomes highly complicated. An example of this latter type of switch is discussed in publication Weng, Hwang: "Distributed double-phase switch", lEE Proceedings-I, Vol. 138, No. 5, October 1991, pp. 417-425.
As known from the art of circuit-switched switches, the Clos architecture is advantageously characterized by low congestion and high modular growability. In conjunction with the ATM communications, however, the need for either buffers or a large number of internal links makes the implementation of the switch complicated. Moreover, since this type of switch provides several alternative routes between a given input and a given output, the computation of an optimal routing set for the different connections during each time slot becomes a clumsy, time-consuming operation, because it needs global (the entire switch covering) information on connection requests related to each time slot. Hence, the internal routing creates a bottle-neck which is limiting to the performance of the switch. In an ATM switch, it is practically impossible to compute such an optimal routing set during the period of a time slot (equal to the period of a cell).
The routing algorithms of a Clos architecture switch have been studied for quite a long time, particularly the so-called randomized-routing algorithms have been a subject of intensive studies due to their simple structure and distributed routing property (by sharing the load of routing over the set of switch elements), whereby they offer an advantageous solution in terms of optimized switch performance. Though this type of randomized-routing algorithm Is capable of reducing congestion in the internal stage(s) of the switch, complete elimination of congestion cannot be attained, because the algorithm is not able to remove internal contentions in the switch. (The term contention herein refers to a case of two or more cells contending simultaneously for access to the same switch element output port.)